package com.ddshuai.easy;

/**
 * @author ddshuai
 * @version 1.0.0
 * @date 2018/3/29
 * @modify desc
 * @2018/3/29 新增        1.0.0
 * 给定一个排序数组和一个目标值，如果在数组中找到目标值则返回索引。如果没有，返回到它将会被按顺序插入的位置。
 * <p>
 * 你可以假设在数组中无重复元素。
 * <p>
 * 输入: [1,3,5,6], 5
 * 输出: 2
 * <p>
 * 输入: [1,3,5,6], 2
 * 输出: 1
 * <p>
 * 输入: [1,3,5,6], 7
 * 输出: 4
 * <p>
 * 输入: [1,3,5,6], 0
 * 输出: 0
 */
public class SearchInsert {

    /**
     * 击败 100%
     * @param nums
     * @param target
     * @return
     */
    public static int searchInsert(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        int middle = (start + end) / 2;
        while (true) {
            if (end == start) {
                if (nums[start] > target) {
                    return start - 1 < 0 ? 0 : start - 1;
                } else if (nums[start] < target) {
                    return end + 1;
                } else {
                    return start;
                }
            }
            if (nums[middle] > target) {
                if (target == nums[start]) {
                    return start;
                }
                end = middle;
                middle = (end + start) / 2;

                if (start == middle) {
                    if (nums[start] > target) {
                        return start;
                    } else {
                        return start + 1;
                    }
                }
            } else if (nums[middle] < target) {
                if (target == nums[end]) {
                    return end;
                }
                start = middle;
                middle = (end + start) / 2;

                if (start == middle) {
                    if (nums[middle] > target) {
                        return middle - 1 < 0 ? 0 : middle - 1;
                    } else {
                        if (nums[end] < target) {
                            return end + 1;
                        }
                        return middle + 1;
                    }
                }
            } else {
                return middle;
            }
        }
    }

    /**
     * 简洁的解法
     * @param nums
     * @param target
     * @return
     */
    public static int searchInsert2(int[] nums, int target) {
        if(nums.length == 0) {
            return 0;
        }
        int result = -1;
        for(int i=0; i<nums.length; i++){
            if(nums[i] == target) {
                return i;
            }
            if(nums[i] > target && result == -1){
                if(i == 0){
                    return 0;
                } else{
                    result = i;
                }
            }
        }
        return result == -1 ? nums.length : result;
    }

    public static void main(String[] args) {
        // 2 1 4 0
        System.out.println(searchInsert(new int[]{1, 3, 5, 6}, 5));
        System.out.println(searchInsert(new int[]{1, 3, 5, 6}, 2));
        System.out.println(searchInsert(new int[]{1, 3, 5, 6}, 7));
        System.out.println(searchInsert(new int[]{1, 3, 5, 6}, 0));
        System.out.println(searchInsert(new int[]{1}, 1));
        System.out.println(searchInsert(new int[]{1, 3}, 2));
    }
}
